#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>

#define MAX_VET 1000

int vet[MAX_VET];
int n_vet=0;
int n_proc=0;
int vet_amostra[100];
int vet_pivots[100];
int mat_r[20][10][10];
int n_pivots=0;
pthread_barrier_t barr;
pthread_barrier_t barr2;
int vet_tam[100];


//quicksort sequencial
void qsort_seq(int array[], int begin, int end) {
   if(end - begin > 0) {
    int aux;
    int pivot = array[begin];
    int left = begin + 1;
    int right = end;
    while(left < right) {
        if(array[left] <= pivot) {
            left++;
        } else {
           // Troca o valor de array[left] com array[right]
           aux = array[left];
           array[left] = array[right];
           array[right] = aux;
           // Fim da troca ( equivale a fun��o swap(array[left], array[right]) )
           right--;
        }
    }
    if(array[left] > pivot) {
        left--;
    }
                                         
    // Troca o valor de array[begin] com array[left]
    aux = array[begin];
    array[begin] = array[left];
    array[left] = aux;
    // Fim da troca ( equivale a fun��o swap(array[begin], array[left]) )
    // Faz as chamadas recursivas para as duas partes da lista
    qsort_seq(array, begin, left-1);
    qsort_seq(array, right, end);
   }
}



//fase 1
void phase1 (int i){

    int part=0;
        int i2;
    part = n_vet/n_proc;
    if (i==(n_proc-1))                 // se for a ultima thread, fica com todo o final do vetor
        qsort_seq(vet,part*i,n_vet-1);
    else        
        qsort_seq(vet,part*i,part*(i+1)-1);
    int c = (n_proc)*i;
    int c2 = part*i;
    for (i2=0;i2<n_proc;i2++){       //preenche o vetor de amostras regulares
        vet_amostra[c+i2] = vet[i*(n_vet/n_proc)+i2*n_vet/(n_proc*n_proc)] ;
    }
 
}

//inicio do psrs
void *psrs(void *threadid){

        phase1((int)threadid);  
        pthread_exit(NULL);
}

//fase 2
void *phase2 (void *threadid){
        coloca_mat(threadid);
        //printf("thread --->>%d",threadid);
        //barrier aqui
        pthread_barrier_wait(&barr);
        troca(threadid);
        pthread_exit(NULL);

}

//preenche a matriz
void coloca_mat(void *threadid){
        int i=0;
        int i2=0;
        int i3=0;
    	int i4=0;
        int j=(int)threadid;
        int k=0;
    	int x=0;
        int part = n_vet/n_proc;
        int c=part*(int)threadid;
       
        
        
        while((i2<n_pivots)&&(i<part)){ 
                while ((vet[c+i]<=vet_pivots[i2]) && (i<part)){  //preenche a matriz com as por�oes limitadas pelos pivots em cada processo
                        mat_r[i3][j][k]=vet[c+i];      
                        i3++;
                        i++;
                }
                i2++;
                k++;
                i3=0;
        }
        if((int)threadid==(n_proc-1)){    //faz o mesmo mas qdo nao ha limitante superior que seja pivo, neste caso final do vetor
                while(c+i<n_vet){
            		if (i2>n_pivots){
            			mat_r[i3][j][k]=vet[c+i];
            			i++;
           				i3++;
           			}
           			else {
           				if (vet[c+i]<=vet_pivots[i2]){  
                        	mat_r[i3][j][k]=vet[c+i];      
                        	i3++;
                        	i++;
                		}
                		else{
                			i2++;
                			i3=0;
                			k++;
                		
                		}
           			}
           			
                }
        }
        else{ //neste caso sem ser final do vetor
                while((c+i)<(part*((int)threadid+1))){
            		mat_r[i3][j][k]=vet[c+i];
            		i++;
            		i3++;
            		
                }
        }
}


//realiza a troca entre as por�oes e o vetor original(fase 3)
int troca (void  *threadid){

    int c=(n_vet/n_proc)*(int)threadid;
    int j=0;
    int i=0;
    int i2=0;
   	int tamanho=0;
    int k = (int)threadid;
    int inicio;
    int vetaux[30];
   
    for (j=0;j<n_proc;j++){//percorre a matriz pegando os elementos de uma determinada faixa de valores definida pelos pivots
        while(mat_r[i][j][k]!=0){
            vetaux[i2]=mat_r[i][j][k];
            i++;
            i2++;
           	tamanho++; 
                                   
        }
        i=0;
    }
    vet_tam[k]=tamanho;
    pthread_barrier_wait(&barr2);// sincroniza�ao necessaria para que todas as threads tenham determinado o tamanho das suas particoes
    for (i2=0;i2<threadid;i2++)
		inicio=inicio+(vet_tam[i2]);
   	qsort_seq(vetaux,0,tamanho-1);// ordena��o sequencial da parti��o composta
   	if(inicio!=0)
   		inicio--;
   	for (i2=0;i2<tamanho;i2++)
   		vet[inicio+i2]=vetaux[i2];//troca
}



int main (int argc, char *argv[]){

    int n_amostras;
    int rc;
    int n = atoi(argv[1]);
    int nthreads = atoi(argv[2]);
    int i;
    pthread_t threads[nthreads];
    n_vet = n;
    n_proc = nthreads;  
        srand (time(NULL));
       

   
    //inicializa o barrier
    pthread_barrier_init(&barr, NULL, nthreads);
	pthread_barrier_init(&barr2, NULL, nthreads);
    //gera os numeros aleatoriamente
    for(i=0;i<n;i++){
        vet[i] = (rand()*(1e2/RAND_MAX))+1;
     }
    //cria os processos da fase 1
    for(i=0;i<(nthreads);i++){
        rc = pthread_create(&threads[i],NULL,psrs,(void *)i);
    }
    for(i=0;i<nthreads;i++)
        pthread_join(threads[i],NULL);  
    
    i=0;
    while (vet_amostra[i]!=0){
        i++;
    }
    //organiza o vetor de amostra
    qsort_seq(vet_amostra,0,i-1);
   	
   	//preenche o vetor de pivots
    for (i=0;i<n_proc;i++){
        if(i==n_proc-1)
            vet_pivots[i] = vet_amostra[i*n_proc+(n_proc/2)];
        else
            vet_pivots[i] = vet_amostra[(i+1)*n_proc+(n_proc/2)-1] ;

    }
    
    n_pivots=n_proc-1;
    //cria os processos da fase 2 em diante
    for(i=0;i<(nthreads);i++){
                rc = pthread_create(&threads[i],NULL,phase2,(void *)i);
        }
    for(i=0;i<nthreads;i++)
        pthread_join(threads[i],NULL);
      
    //saida especificada
    for(i=0;i<n_vet;i++){
        if(i==n_vet-1)
            printf("%d.",vet[i]);
        else
            printf("%d, ",vet[i]);
    }

        return 1;

}

